package com.qjc.demo.train.dp;

/**
 * @ClassName: Fiber2
 * @Description: 斐波那契数列：递归分治+记忆搜索（备忘录）
 * @Author: qjc
 * @Date: 2022/5/4 2:05 PM
 */
public class Fiber2 {

    // 用于存储每次计算的结果
    static long[] sub = new long[100];

    public static long fib(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        if (sub[n] == 0) {
            // 没计算过
            sub[n] = fib(n - 1) + fib(n - 2);
        }
        // 计算过，直接返回
        return sub[n];
    }

    public static void main(String[] args) {
        System.out.println(fib(64));
    }

}
